package com.example.algorithm.huawei_rongyao_29;

import java.util.PriorityQueue;
import java.util.Scanner;

// 分金条的最小花费
/**
 * 给定一个正数数组arr，arr的累加和代表金条的总长度，arr的每个数代表金条要分成的长度。
 * 规定长度为k的金条分成两块，费用为k个铜板。返回把金条分出arr中的每个数字需要的最小代价。这是算钱的规则。
 * 就是说，你要把完整的一条金条分成arr那样的一份份，但是力求花钱最少。
 * [要求]
 * 时间复杂度为，空间复杂度为
 *
 * 输入描述:
 * 第一行一个整数N。表示数组长度。
 * 接下来一行N个整数，表示arr数组。
 * 输出描述:
 * 一个整数表示最小代价，也就是多少钱。
 *
 *这个问题可以通过构建最小堆来解决。
 * 首先，将输入的数组转换为一个最小堆（优先队列），最小堆就是顶上的值是整个数组中的最小值。
 * 然后反复从堆中取出两个最小的元素（代表需要分割的金条），合并它们并计算合并的代价，将新的金条长度放回堆中。
 * 重复这个过程直到堆中只剩下一个元素，这个元素就是最终合并完成的金条，返回累计的代价即可。
 *
 * 这个程序读取输入的数组，并使用最小堆来表示金条的长度。
 * 然后反复从堆中取出两个最小的金条，合并它们并计算合并的代价，将新的金条长度放回堆中，直到堆中只剩下一个元素，最终返回累计的代价。
 * */

public class Q03_MinCostForGoldBar {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 数组长度
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt(); // 遍历输入数组n个元素
        }
        int minCost = minCostForGoldBar(arr);
        System.out.println(minCost);
        scanner.close();
    }

    public static int minCostForGoldBar(int[] arr) {

        // 构建最小堆
        // 我傻眼了，直接就用现成的已有的api构建出一个堆啦???
        // 在 Java 中，minHeap.offer(num) 方法用于将一个元素插入到最小堆（Min Heap）中。offer 方法是 PriorityQueue 类的一部分，PriorityQueue 是一个实现了优先级队列的数据结构，它本质上是一个基于堆（heap）的集合。PriorityQueue 默认情况下是一个最小堆，这意味着队列中的每个元素都小于或等于其子元素。
        //offer 方法的具体作用如下：
        //插入元素：将指定的元素插入到优先级队列中。
        //调整堆结构：插入元素后，重新调整堆结构以保持最小堆的性质。
        //返回值：该方法返回一个布尔值 true，表示元素已成功插入队列。
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.offer(num);
        }

        int totalCost = 0;
        while (minHeap.size() > 1) {
            // 取出两个最小的元素（金条）
            // 在 Java 中，minHeap.poll() 方法用于从最小堆（Min Heap）中移除并返回堆顶元素。
            // 具体来说，poll 方法的作用包括以下几点：
            //移除元素：从优先级队列（最小堆）中移除堆顶元素，即队列中的最小元素。
            //返回值：返回被移除的元素。如果队列为空，则返回 null。
            //调整堆结构：移除元素后，重新调整堆结构以保持最小堆的性质。
            int bar1 = minHeap.poll();
            int bar2 = minHeap.poll();
            // 合并金条并计算合并代价
            int newBar = bar1 + bar2;
            totalCost += newBar;
            // 将合并后的金条放回堆中
            minHeap.offer(newBar);
        }
        return totalCost;
    }
}

